package com.xzz.bfs;

import com.xzz.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: hhz
 * @create: 2022-01-11 10:18
 * 111. 二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 **/
public class MinDepth {
    public static void main(String[] args) {
//        TreeNode node1 = new TreeNode(3);
//        TreeNode node2 = new TreeNode(9);
//        TreeNode node3 = new TreeNode(20);
//        TreeNode node4 = new TreeNode(15);
//        TreeNode node5 = new TreeNode(7);
//        node1.setLeft(node2);
//        node1.setRight(node3);
//        node3.setRight(node4);
//        node4.setLeft(node5);
//        System.out.println(minDepth(node1));

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        System.out.println(minDepth(node1));

    }
    public static int minDepth(TreeNode root) {
        if(null==root){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 1;
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode poll = queue.poll();

                TreeNode left = poll.getLeft();
                TreeNode right = poll.getRight();
                if(left==null && right==null){
                   return res;
                }
                if(null!=left){
                    queue.offer(left);
                }
                if(null!=right){
                    queue.offer(right);
                }
            }
            res++;

        }
        return res;
    }
}
